{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #导航装置"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #dynamic-programming #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #动态规划 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: navigation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #导航装置"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "小扣参加的秋日市集景区共有 $N$ 个景点，景点编号为 $1$~$N$。景点内设有 $N-1$ 条双向道路，使所有景点形成了一个二叉树结构，根结点记为 `root`，景点编号即为节点值。\r\n",
    "\r\n",
    "由于秋日市集景区的结构特殊，游客很容易迷路，主办方决定在景区的若干个景点设置导航装置，按照所在景点编号升序排列后定义装置编号为 1 ~ M。导航装置向游客发送数据，数据内容为列表 `[游客与装置 1 的相对距离,游客与装置 2 的相对距离,...,游客与装置 M 的相对距离]`。由于游客根据导航装置发送的信息来确认位置，因此主办方需保证游客在每个景点接收的数据信息皆不相同。请返回主办方最少需要设置多少个导航装置。\r\n",
    "\r\n",
    "**示例 1：**\r\n",
    ">输入：`root = [1,2,null,3,4]`\r\n",
    ">\r\n",
    ">输出：`2`\r\n",
    ">\r\n",
    ">解释：在景点 1、3 或景点 1、4 或景点 3、4 设置导航装置。\r\n",
    ">\r\n",
    ">![image.png](https://pic.leetcode-cn.com/1597996812-tqrgwu-image.png){:height=\"250px\"}\r\n",
    "\r\n",
    "\r\n",
    "\r\n",
    "**示例 2：**\r\n",
    ">输入：`root = [1,2,3,4]`\r\n",
    ">\r\n",
    ">输出：`1`\r\n",
    ">\r\n",
    ">解释：在景点 3、4 设置导航装置皆可。\r\n",
    ">\r\n",
    ">![image.png](https://pic.leetcode-cn.com/1597996826-EUQRyz-image.png){:height=\"200px\"}\r\n",
    "\r\n",
    "\r\n",
    "\r\n",
    "**提示：**\r\n",
    "- `2 <= N <= 50000`\r\n",
    "- 二叉树的非空节点值为 `1~N` 的一个排列。\r\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [hSRGyL](https://leetcode.cn/problems/hSRGyL/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [hSRGyL](https://leetcode.cn/problems/hSRGyL/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,null,3,4]', '[1,2,3,4]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TreeNode:\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = 0\n",
    "        self.s = 1\n",
    "\n",
    "    def dfs(self, root: TreeNode) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        \n",
    "        l = self.dfs(root.left)\n",
    "        r = self.dfs(root.right)\n",
    "        \n",
    "        if root.left and root.right:\n",
    "            self.res += not l and not r\n",
    "            self.s = not (l and r)\n",
    "            return 1\n",
    "        return l or r\n",
    "\n",
    "    def navigation(self, root: TreeNode) -> int:\n",
    "        l = self.dfs(root.left)\n",
    "        r = self.dfs(root.right)\n",
    "        \n",
    "        return self.res + (0 if (l and r) else self.s)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def navigation(self, root: TreeNode) -> int:\n",
    "        self.res = 0\n",
    "        self.s = 1 # 根是否要加一个\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return False\n",
    "            l = dfs(node.left)\n",
    "            r = dfs(node.right)\n",
    "            # 这是一个三叉\n",
    "            if node.left and node.right:\n",
    "                # 左右如果目前都没有，那必须左右至少有一个\n",
    "                if (not l) and (not r):\n",
    "                    self.res += 1\n",
    "                \n",
    "                # 左右不是俩都有，那无论如何根得加一个\n",
    "                if not (l and r):\n",
    "                    self.s = 1\n",
    "                else:\n",
    "                    self.s = 0\n",
    "                \n",
    "                return True\n",
    "                \n",
    "            return l or r\n",
    "\n",
    "        l = dfs(root.left)\n",
    "        r = dfs(root.right)\n",
    "\n",
    "        print(self.s)\n",
    "        if l and r:\n",
    "            return self.res\n",
    "        else:\n",
    "            return self.res + self.s\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    ans = 0\n",
    "    s = 1\n",
    "    def dsf(self,node):\n",
    "        if node is None:\n",
    "            return False;\n",
    "        left = self.dsf(node.left)\n",
    "        right = self.dsf(node.right)\n",
    "        if node.left and node.right:\n",
    "            if (not left) and (not right):\n",
    "                self.ans += 1\n",
    "            if not(left and right):\n",
    "                self.s = 1\n",
    "            else:\n",
    "                self.s = 0\n",
    "            return True\n",
    "        return left or right;\n",
    "    def navigation(self, root: TreeNode) -> int:\n",
    "        l = self.dsf(root.left)\n",
    "        r = self.dsf(root.right)\n",
    "        self.s = 0 if ( l and r ) else self.s\n",
    "        return self.ans + self.s\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def navigation(self, root: TreeNode) -> int:\n",
    "        self.res = 0\n",
    "        self.add = 1\n",
    "        def dfs(node: TreeNode):\n",
    "            if not node:\n",
    "                return False\n",
    "            l = dfs(node.left)\n",
    "            r = dfs(node.right)\n",
    "            if node.left and node.right:\n",
    "                if not l and not r:\n",
    "                    self.res += 1\n",
    "\n",
    "                if not (l and r):\n",
    "                    self.add = 1\n",
    "                else:\n",
    "                    self.add = 0\n",
    "                return True\n",
    "            return l or r\n",
    "\n",
    "        l = dfs(root.left)\n",
    "        r = dfs(root.right)\n",
    "\n",
    "        if l and r:\n",
    "            return self.res\n",
    "\n",
    "        else:\n",
    "            return self.res + self.add"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def navigation(self, root: TreeNode) -> int:\n",
    "        self.ret=0\n",
    "        # 标记root及其子树有没有导航\n",
    "        def dfs(root:TreeNode):\n",
    "            if not root:\n",
    "                return 0\n",
    "            lflag=dfs(root.left)\n",
    "            rflag=dfs(root.right)\n",
    "            if root.left and root.right:\n",
    "                if lflag==0 and rflag==0:\n",
    "                    self.ret+=1\n",
    "                    return 1\n",
    "                elif lflag==0 or rflag==0:\n",
    "                    return 1\n",
    "                else:\n",
    "                    return 2\n",
    "            elif root.left:\n",
    "                return lflag\n",
    "            elif root.right:\n",
    "                return rflag\n",
    "            else:\n",
    "                return 0\n",
    "        lflag=dfs(root.left)\n",
    "        rflag=dfs(root.right)\n",
    "        if lflag+rflag<2:\n",
    "            self.ret+=1\n",
    "        return self.ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def navigation(self, root: TreeNode) -> int:\n",
    "        self.res = 0\n",
    "        self.s = 1 # 根是否要加一个\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return False\n",
    "            l = dfs(node.left)\n",
    "            r = dfs(node.right)\n",
    "            # 这是一个三叉\n",
    "            if node.left and node.right:\n",
    "                # 左右如果目前都没有，那必须左右至少有一个\n",
    "                if (not l) and (not r):\n",
    "                    self.res += 1\n",
    "                \n",
    "                # 左右不是俩都有，那无论如何根得加一个\n",
    "                if not (l and r):\n",
    "                    self.s = 1\n",
    "                else:\n",
    "                    self.s = 0\n",
    "                \n",
    "                return True\n",
    "                \n",
    "            return l or r\n",
    "\n",
    "        l = dfs(root.left)\n",
    "        r = dfs(root.right)\n",
    "\n",
    "        # 如果左右都有，根就不需要了\n",
    "        if l and r:\n",
    "            return self.res\n",
    "        # 如果左右只有一个，那么我们就拿那棵没有的树当父树然后 + s（对父树有需求+1，没需求不加）\n",
    "        else:\n",
    "            return self.res + self.s\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def navigation(self, root: TreeNode) -> int:\n",
    "        self.res = 0\n",
    "        self.s = 1 # 根是否要加一个\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return False\n",
    "            l = dfs(node.left)\n",
    "            r = dfs(node.right)\n",
    "            # 这是一个三叉\n",
    "            if node.left and node.right:\n",
    "                # 左右如果目前都没有，那必须左右至少有一个\n",
    "                if (not l) and (not r):\n",
    "                    self.res += 1\n",
    "                \n",
    "                # 左右不是俩都有，那无论如何根得加一个\n",
    "                if not (l and r):\n",
    "                    self.s = 1\n",
    "                else:\n",
    "                    self.s = 0\n",
    "                \n",
    "                return True\n",
    "                \n",
    "            return l or r\n",
    "\n",
    "        l = dfs(root.left)\n",
    "        r = dfs(root.right)\n",
    "\n",
    "        if l and r:\n",
    "            return self.res\n",
    "        else:\n",
    "            return self.res + self.s\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def navigation(self, root: TreeNode) -> int:\n",
    "        self.res = 0\n",
    "        self.s = 1 # 根是否要加一个\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return False\n",
    "            l = dfs(node.left)\n",
    "            r = dfs(node.right)\n",
    "            # 这是一个三叉\n",
    "            if node.left and node.right:\n",
    "                # 左右如果目前都没有，那必须左右至少有一个\n",
    "                if (not l) and (not r):\n",
    "                    self.res += 1\n",
    "                \n",
    "                # 左右不是俩都有，那无论如何根得加一个\n",
    "                if not (l and r):\n",
    "                    self.s = 1\n",
    "                else:\n",
    "                    self.s = 0\n",
    "                \n",
    "                return True\n",
    "                \n",
    "            return l or r\n",
    "\n",
    "        l = dfs(root.left)\n",
    "        r = dfs(root.right)\n",
    "\n",
    "        # 如果左右都有，根就不需要了\n",
    "        if l and r:\n",
    "            return self.res\n",
    "        # 如果左右只有一个，那么我们就拿那棵没有的树当父树然后 + s（对父树有需求+1，没需求不加）\n",
    "        else:\n",
    "            return self.res + self.s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = 0\n",
    "    def navigation(self, root: TreeNode) -> int:\n",
    "        self.res = 0\n",
    "        def dfs(cur):\n",
    "            if not cur:\n",
    "                return 0\n",
    "            left = dfs(cur.left)\n",
    "            right = dfs(cur.right)\n",
    "            if not cur.left:\n",
    "                return right\n",
    "            if not cur.right:\n",
    "                return left\n",
    "            # 三叉点\n",
    "            if (left== 0 and right == 0):\n",
    "                self.res += 1\n",
    "                return 1\n",
    "            if left == 0 or right == 0:\n",
    "                return 1\n",
    "            return 2\n",
    "        if not root:\n",
    "            return 0\n",
    "        left = dfs(root.left)\n",
    "        right = dfs(root.right)\n",
    "        if (left + right >= 2):\n",
    "            return self.res\n",
    "        return self.res + 1\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def navigation(self, root: TreeNode) -> int:\n",
    "        self.res = 0\n",
    "        self.s = 1 # 根是否要加一个\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return False\n",
    "            l = dfs(node.left)\n",
    "            r = dfs(node.right)\n",
    "            # 这是一个三叉\n",
    "            if node.left and node.right:\n",
    "                # 左右如果目前都没有，那必须左右至少有一个\n",
    "                if (not l) and (not r):\n",
    "                    self.res += 1\n",
    "                \n",
    "                # 左右不是俩都有，那无论如何根得加一个\n",
    "                if not (l and r):\n",
    "                    self.s = 1\n",
    "                else:\n",
    "                    self.s = 0\n",
    "                \n",
    "                return True\n",
    "                \n",
    "            return l or r\n",
    "\n",
    "        l = dfs(root.left)\n",
    "        r = dfs(root.right)\n",
    "\n",
    "        # 如果左右都有，根就不需要了\n",
    "        if l and r:\n",
    "            return self.res\n",
    "        # 如果左右只有一个，那么我们就拿那棵没有的树当父树然后 + s（对父树有需求+1，没需求不加）\n",
    "        else:\n",
    "            return self.res + self.s\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "\n",
    "    def navigation(self, root: TreeNode) -> int:\n",
    "        if not root: return 0\n",
    "        self.res = 0\n",
    "\n",
    "        def dfs(node):\n",
    "            if node is None: return 0\n",
    "\n",
    "            # 1 叶子节点，返回0，表示可能要部署，但是先不部署。\n",
    "            if node.left is None and node.right is None:\n",
    "                return 0\n",
    "            # 2, 直接去掉度为2的node，这里保证传递的都是非None的\n",
    "            if node.left is None:\n",
    "                return dfs(node.right)\n",
    "            if node.right is None:\n",
    "                return dfs(node.left)\n",
    "            # 3，度为3的，需要考虑左右子树，至少一个有部署，剩下那个，先不部署，让上面同意协商。间接去掉度为3的node\n",
    "            l, r = dfs(node.left), dfs(node.right)\n",
    "            if l == 0 and r == 0:\n",
    "                self.res += 1  # 部署1个\n",
    "                return 1  # ！！！ 这里要返回1，因为其实对于上面，这边是部署了1个\n",
    "            if l == 0 and r > 0:\n",
    "                return 1\n",
    "            if l > 0 and r == 0:\n",
    "                return l\n",
    "            return 2  # 无论部署2个还是1个分支，上传1，表示已经部署了，对于上面来说，不感知的？？ # 实际上是感知的，就是最后一个root节点感知。\n",
    "            \n",
    "\n",
    "        # root 不可能度为3\n",
    "        l, r = dfs(root.left), dfs(root.right)\n",
    "        if l == 0 and r == 0:\n",
    "            return self.res +1\n",
    "        if l == 0 and r == 1 or l == 1 and r == 0:\n",
    "            return self.res +1\n",
    "        return self.res\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def navigation(self, root: TreeNode) -> int:\n",
    "        def get(node):\n",
    "            if node is None:\n",
    "                return [0, 1, 1, 1]\n",
    "            elif hasattr(node, 'result'):\n",
    "                return node.result\n",
    "            if not node.left and not node.right:\n",
    "                result = [0, 1, 1, 1]\n",
    "            elif not node.left or not node.right:\n",
    "                result = get(node.left) if node.left else get(node.right)\n",
    "                result[1] = min(result[0] + 1, result[3])\n",
    "            else:\n",
    "                result = [0xffffffff] * 4\n",
    "                l, r = get(node.left), get(node.right)\n",
    "                result[3] = min(l[1] + r[3], l[3] + r[1], l[2] + r[2])\n",
    "                result[2] = min(result[3], l[0] + r[2], l[2] + r[0])\n",
    "                result[1] = min(result[3], l[0] + r[3], l[3] + r[0])\n",
    "                result[0] = min(result[1], result[2], l[0] + r[2], l[2] + r[0])\n",
    "            setattr(node, 'result', result)\n",
    "            return node.result\n",
    "\n",
    "        return get(root)[1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def navigation(self, root: TreeNode) -> int:\n",
    "        def get(node):\n",
    "            if node is None:\n",
    "                return [0, 1, 1, 1]\n",
    "            elif hasattr(node, 'result'):\n",
    "                return node.result\n",
    "            if not node.left and not node.right:\n",
    "                result = [0, 1, 1, 1]\n",
    "            elif not node.left or not node.right:\n",
    "                result = get(node.left) if node.left else get(node.right)\n",
    "                result[1] = min(result[0] + 1, result[3])\n",
    "            else:\n",
    "                result = [0xffffffff] * 4\n",
    "                l, r = get(node.left), get(node.right)\n",
    "                result[3] = min(l[1] + r[3], l[3] + r[1], l[2] + r[2])\n",
    "                result[2] = min(result[3], l[0] + r[2], l[2] + r[0])\n",
    "                result[1] = min(result[3], l[0] + r[3], l[3] + r[0])\n",
    "                result[0] = min(result[1], result[2], l[0] + r[2], l[2] + r[0])\n",
    "            setattr(node, 'result', result)\n",
    "            return node.result\n",
    "\n",
    "        return get(root)[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def navigation(self, root: TreeNode) -> int:\n",
    "        def get(node):\n",
    "            if node is None:\n",
    "                return [0, 1, 1, 1]\n",
    "            elif hasattr(node, 'result'):\n",
    "                return node.result\n",
    "            if not node.left and not node.right:\n",
    "                result = [0, 1, 1, 1]\n",
    "            elif not node.left or not node.right:\n",
    "                result = get(node.left) if node.left else get(node.right)\n",
    "                result[1] = min(result[0] + 1, result[3])\n",
    "            else:\n",
    "                result = [0xffffffff] * 4\n",
    "                l, r = get(node.left), get(node.right)\n",
    "                result[3] = min(l[1] + r[3], l[3] + r[1], l[2] + r[2])\n",
    "                result[2] = min(result[3], l[0] + r[2], l[2] + r[0])\n",
    "                result[1] = min(result[3], l[0] + r[3], l[3] + r[0])\n",
    "                result[0] = min(result[1], result[2], l[0] + r[2], l[2] + r[0])\n",
    "            setattr(node, 'result', result)\n",
    "            return node.result\n",
    "\n",
    "        return get(root)[1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def navigation(self, root: TreeNode) -> int:\n",
    "\n",
    "        @cache\n",
    "        def dp(node: TreeNode) -> int:\n",
    "            if not node.left and not node.right:\n",
    "                return 0\n",
    "            if node.left and node.right:\n",
    "                l = dp(node.left)\n",
    "                r = dp(node.right)\n",
    "                if l == 0 and r == 0:\n",
    "                    return 1\n",
    "                return l + r\n",
    "            elif node.left:\n",
    "                l = dp(node.left)\n",
    "                return l\n",
    "            elif node.right:\n",
    "                r = dp(node.right)\n",
    "                return r\n",
    "\n",
    "        def get_double(r: TreeNode) -> TreeNode:\n",
    "            if not r:\n",
    "                return None\n",
    "            if r.left and r.right:\n",
    "                return r\n",
    "            elif r.left:\n",
    "                return get_double(r.left)\n",
    "            elif r.right:\n",
    "                return get_double(r.right)\n",
    "            else:\n",
    "                return None\n",
    "\n",
    "        # if root.left and not root.right:\n",
    "        #     double_node = get_double(root.left)\n",
    "        #     if not double_node:\n",
    "        #         return 1\n",
    "        #     else:\n",
    "        #         if dp(double_node.left) and dp(double_node.right):\n",
    "        #             return dp(double_node.left) + dp(double_node.right)\n",
    "        #         else:\n",
    "        #             return dp(double_node.left) + dp(double_node.right) + 1\n",
    "        # elif root.right and not root.left:\n",
    "        #     double_node = get_double(root.right)\n",
    "        #     if not double_node:\n",
    "        #         return 1\n",
    "        #     else:\n",
    "        #         if dp(double_node.left) and dp(double_node.right):\n",
    "        #             return dp(double_node.left) + dp(double_node.right)\n",
    "        #         else:\n",
    "        #             return dp(double_node.left) + dp(double_node.right) + 1\n",
    "        # else:\n",
    "        d_left = get_double(root.left)\n",
    "        d_right = get_double(root.right)\n",
    "        if d_left and not d_right:\n",
    "            double_node = d_left\n",
    "            if not double_node:\n",
    "                return 1\n",
    "            else:\n",
    "                if dp(double_node.left) and dp(double_node.right):\n",
    "                    return dp(double_node)\n",
    "                else:\n",
    "                    return dp(double_node) + 1\n",
    "        elif d_right and not d_left:\n",
    "            double_node = d_right\n",
    "            if not double_node:\n",
    "                return 1\n",
    "            else:\n",
    "                if dp(double_node.left) and dp(double_node.right):\n",
    "                    return dp(double_node)\n",
    "                else:\n",
    "                    return dp(double_node) + 1\n",
    "        elif d_right and d_left:\n",
    "            return dp(d_left) + dp(d_right)\n",
    "        else:\n",
    "            return 1\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "def log_output(func):\n",
    "    def wrap(*args, **kwargs):\n",
    "        res = func(*args, **kwargs)\n",
    "        print(res, args[1:], kwargs)\n",
    "        return res\n",
    "    return wrap\n",
    "\n",
    "class Solution:\n",
    "    def navigation(self, root: TreeNode) -> int:\n",
    "        min_cnt, need_top = self.navigation_(root, is_root=True)\n",
    "        return max(1, min_cnt + need_top)\n",
    "\n",
    "    # @log_output\n",
    "    def navigation_(self, root: TreeNode, is_root=False) -> int:\n",
    "        if root is None:\n",
    "            return (0, 0)\n",
    "\n",
    "        left_min_cnt, left_need_top = self.navigation_(root.left)\n",
    "        right_min_cnt, right_need_top = self.navigation_(root.right)\n",
    "\n",
    "        if root.left is not None and root.right is not None:\n",
    "            marked_child_n = 0\n",
    "            if left_min_cnt > 0:\n",
    "                marked_child_n += 1\n",
    "            if right_min_cnt > 0:\n",
    "                marked_child_n += 1\n",
    "            if marked_child_n == 2:\n",
    "                # 两个路都已经有了，不用慌了, top路也一笔勾销\n",
    "                return (left_min_cnt + right_min_cnt, 0)\n",
    "            elif marked_child_n == 1:\n",
    "                if is_root:\n",
    "                    return (left_min_cnt + right_min_cnt, left_need_top + right_need_top)\n",
    "                else:\n",
    "                    # 上面还欠一个\n",
    "                    return (left_min_cnt + right_min_cnt, 1)\n",
    "            else:\n",
    "                if is_root:\n",
    "                    return (left_min_cnt + right_min_cnt + 1, left_need_top + right_need_top)\n",
    "                else:\n",
    "                    # 底下随便放一个，上面欠一个\n",
    "                    return (left_min_cnt + right_min_cnt + 1, 1)\n",
    "        elif root.left is not None or root.right is not None:\n",
    "            # 单线，往上传\n",
    "            return (left_min_cnt + right_min_cnt, min(left_need_top + right_need_top, 1))\n",
    "        else:\n",
    "            # 叶子节点\n",
    "            return (0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def navigation(self, root: TreeNode) -> int:\n",
    "\n",
    "        @cache\n",
    "        def dp(node: TreeNode) -> int:\n",
    "            if not node.left and not node.right:\n",
    "                return 0\n",
    "            if node.left and node.right:\n",
    "                l = dp(node.left)\n",
    "                r = dp(node.right)\n",
    "                if l == 0 and r == 0:\n",
    "                    return 1\n",
    "                return l + r\n",
    "            elif node.left:\n",
    "                l = dp(node.left)\n",
    "                return l\n",
    "            elif node.right:\n",
    "                r = dp(node.right)\n",
    "                return r\n",
    "\n",
    "        def get_double(r: TreeNode) -> TreeNode:\n",
    "            if not r:\n",
    "                return None\n",
    "            if r.left and r.right:\n",
    "                return r\n",
    "            elif r.left:\n",
    "                return get_double(r.left)\n",
    "            elif r.right:\n",
    "                return get_double(r.right)\n",
    "            else:\n",
    "                return None\n",
    "\n",
    "        d_left = get_double(root.left)\n",
    "        d_right = get_double(root.right)\n",
    "        if d_left and not d_right:\n",
    "            double_node = d_left\n",
    "            if not double_node:\n",
    "                return 1\n",
    "            else:\n",
    "                if dp(double_node.left) and dp(double_node.right):\n",
    "                    return dp(double_node)\n",
    "                else:\n",
    "                    return dp(double_node) + 1\n",
    "        elif d_right and not d_left:\n",
    "            double_node = d_right\n",
    "            if not double_node:\n",
    "                return 1\n",
    "            else:\n",
    "                if dp(double_node.left) and dp(double_node.right):\n",
    "                    return dp(double_node)\n",
    "                else:\n",
    "                    return dp(double_node) + 1\n",
    "        elif d_right and d_left:\n",
    "            return dp(d_left) + dp(d_right)\n",
    "        else:\n",
    "            return 1\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def navigation(self, root: TreeNode) -> int:\n",
    "        \n",
    "        #parent方向没有装置，parent方向有装置的情况下，需要安装数量\n",
    "        def dfs(root,hasp):\n",
    "            if not root.left and not root.right:\n",
    "                return (1,0)\n",
    "            if not root.left:\n",
    "                return dfs(root.right,True)\n",
    "            if not root.right:\n",
    "                return dfs(root.left,True)\n",
    "            l0,l1=dfs(root.left,True)\n",
    "            r0,r1=dfs(root.right,True)\n",
    "\n",
    "            #根节点和非根节点分开判断\n",
    "            #对三叉路节点(比如除了根节点以外有两个孩子的)，保证至少两个方向有装置。\n",
    "            #对两岔路节点，至少1个方向有装置(比如有两个孩子的根节点或者有1个孩子的其他节点)。\n",
    "            if not hasp:\n",
    "                #parent方向没有装置的情况下，左右子树至少其中一个有装置\n",
    "                #有一种情况是即使parent有装置，l1和r1也都不为0，此时l1+r1可能是更小的\n",
    "                return (min(max(l0,1)+r1,max(r0,1)+l1,max(l1,1)+max(r1,1)),-1)\n",
    "            else:\n",
    "                #左右子树必须都有装置\n",
    "                ret0=max(l1,1)+max(r1,1)\n",
    "                #parent方向有装置的情况下，左右子树至少其中一个有装置\n",
    "                ret1=min(max(l1,1)+r1,max(r1,1)+l1)\n",
    "                return(ret0,ret1)\n",
    "        return dfs(root,False)[0]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
